package org.example.myleet.p797;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(graph, 0, n - 1, path, result);
        return result;
    }

    private void dfs(int[][] graph, int from, int end, List<Integer> path, List<List<Integer>> result) {
        if (from == end) {
            //到达终点，把路径深拷贝后加入到结果中
            List<Integer> clone = new ArrayList<>(path);
            result.add(clone);
            return;
        }
        int[] edges = graph[from];
        for (int to : edges) {
            int pathSize = path.size();
            //下一个节点加入到路径中
            path.add(to);
            //继续DFS
            dfs(graph, to, end, path, result);
            //回溯
            path.remove(pathSize);
        }
    }
}
